perm filename RLISP.ACH[S,DOC] blob
sn#183577 filedate 1975-10-31 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00020 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00004 00002 STANFORD ARTIFICIAL INTELLIGENCE LABORATORY October 1970
C00006 00003 1
C00008 00004 2
C00011 00005 3
C00014 00006 4
C00017 00007 5
C00020 00008 6
C00023 00009 7
C00026 00010 8
C00029 00011 9
C00032 00012 10
C00035 00013 11
C00039 00014 12
C00043 00015 13
C00048 00016 14
C00052 00017 15
C00053 00018 16
C00056 00019 17
C00058 00020 18
C00059 ENDMK
C⊗;
STANFORD ARTIFICIAL INTELLIGENCE LABORATORY October 1970
OPERATING NOTE 62
R E D U C E 2
S Y M B O L I C M O D E
P R I M E R*
by
Anthony C. Hearn
University of Utah
*This research was sponsored by the Advanced Research Projects Agency
of the Department of Defense under Contract No. F30602-70-C-0300 at
the University of Utah, and under Contract No. SD-183 at Stanford
University.
1
1. INTRODUCTION
REDUCE is a program designed primarily for general algebraic
computations of interest to mathematicians, physicists and engineers.
However, its source language is general enough to allow for a full
range of LISP-like symbolic calculations. This primer is a brief
guide to this source language. It does not describe the algebraic
capabilities of the system, so anyone interested in these should
consult the REDUCE 2 User's Manual [1], of which this primer is an
extract.
This primer assumes that the reader has a reasonable
acquaintance with LISP 1.5 at the level of the LISP 1.5 Programmer's
Manual [2] or Clark Weissman's LISP 1.5 Primer[3]. Anyone unfamiliar
with this material is advised to study it before proceeding further.
In Section 2 of this primer, we give details of the basic
structure of REDUCE programs. Finally, in Section 3, details of
running REDUCE symbolic programs on the Stanford PDP-10 is given.
The author would appreciate hearing from any users who
experience trouble with the system (please include copies of relevant
input and output).
2
2. STRUCTURE OF PROGRAMS
2.1 Preliminary
A REDUCE program consists of a set of functional commands
which are evaluated sequentially by the computer. These commands are
composed from declarations, statements and expressions, which in turn
are sequences of numbers, variables, operators, strings, reserved
words and delimiters (such as commas and parentheses).
2.2 Numbers
Numbers in REDUCE may be of two types; integer and real.
Integers consist of a signed or unsigned sequence of decimal digits
written without a decimal point.
e. g. -2, 5396, +32
Real numbers may be written in two ways;
i) as a signed or unsigned sequence of 1-9 decimal digits with
an embedded decimal point.
ii) as in 1) followed by a decimal exponent which is written as
the letter E followed by a signed or unsigned integer.
e. g. 32. +32.0 0.32E2 and 320.E-1 are all representations of 32.
Restriction:
The unsigned part of any number may NOT begin with a decimal point.
i. e. NOT ALLOWED .5 -.23 +.12
2.3 Identifiers
Identifiers in REDUCE consist of one to twenty-four
alphanumeric characters (i.e. upper case alphabetic letters or
decimal digits) the first of which must be alphabetic.
e. g. A AZ P1 Q23P AVERYLONGVARIABLE
It is also possible to include non-alphanumeric characters in
identifiers by prefixing the character by an exclamation mark.
e. g., DSK!: GET!*!* A!+B
Identifiers are used as variables, labels and to name operators,
arrays and procedures.
Restrictions:
Reserved words in REDUCE (see Section 2.9) may not be used as
identifiers. No spaces may appear within an identifier, and an
3
identifier may not extend over a line of text.
2.4 Variables
Variables are a particular type of identifier, and are
specified by name and type. Their names must be allowed
identifiers. There are several variable types allowed, and these
are discussed later in Section 2.11.1.
2.5 Operators
Operators in REDUCE are also specified by name and type.
There are two types, infix and prefix.
Infix operators occur between their arguments.
e. g. A + B - C
U . V
The following infix operators are built into the system.
<infix operator> ::= ←|∧|∨|ε|=|≠|≡|>=|>|<=|<|+|-|*|/|↑|.
For compatibility with the intermediate language used by
REDUCE, each infix operator has an alphanumeric identifier associated
with it. These identifiers may be used interchangably with the
corresponding infix character(s) on input. This correspondence is as
follows:
← SETQ
∧ AND
∨ OR
ε MEMBER
= EQUAL
≠ UNEQ
≡ EQ
>= GREATEQ
> GREATERP
<= LESSEQ
< LESSP
+ PLUS
- MINUS
* TIMES
/ QUOTIENT
↑ EXPT
. CONS
In systems which do not have all these characters, the
alphanumeric name may be used instead. In addition, the following
alternative forms are allowed
4
operator alternative
↑ **
← :=
These operators may be further divided into the following sub
classes
<logical operator> ::= ∧|∨
<relational operator> ::= ε|=|≠|≡|>=|>|<=|<
<arithmetic operator> ::= +|-|*|/|↑
<symbolic operator> ::= .
The above operators may take any number of arguments, except
- which is unary, and . , ↑ and / which are binary. The expression
A-B is interpreted as A+-B on input. Furthermore, A.B.C.D is
interpreted as A.(B.(C.D)) and similarly with ↑ and /.
Parentheses may be used to specify the order of combination. If
parentheses are omitted then this order is by the precedence ordering
given by the above list (from outermost to innermost operations).
The user may add new single character infix operators to the system
by the declaration INFIX.
e. g. INFIX ∀,∃; adds infix operators ∀ and ∃ to the system.
These new operators will be given the lowest precedence and will be
ordered among themselves by their order at definition. Thus ∀ has a
higher precedence than ∃.
Restriction:
Because of their particular uses in the system, the
characters !, λ and ¬ cannot be used as infix operators.
The precedence of any infix operator may be changed by the
declaration PRECEDENCE.
e. g. PRECEDENCE ∀,=;
gives ∀ a new precedence immediately higher than the current
precedence of =.
Prefix operators occur at the head of their arguments, which
are written as a list enclosed in parentheses and separated by
commas, as with normal mathematical functions.
e. g. CAR(U)
CDR (REVERSE (U))
Parentheses may be omitted if the operator is unary.
5
e. g. CAR Y and CAR(Y) are equivalent.
Such unary operators have a precedence higher than any infix operator.
Infix operators may also be used in a prefix format on input.
On output, however, they will always be printed in an infix form.
2.6 Strings
Strings are used only in output statements. A string consists
of any number of characters enclosed in double quotes.
e. g. "A STRING"
2.7 Comments
Comments are useful for including explanatory material at
various points in a program. They may be used in the following form:
COMMENT <any sequence of characters not including a terminator>
<terminator>
where
<terminator> ::= ;|$
e. g. COMMENT THIS IS A COMMENT;
In addition, the sequence of symbols
END <any sequence of symbols not including a terminator or the
reserved words END, ELSE or UNTIL>
is equivalent to the reserved word END.
2.8 Expressions
REDUCE expressions may be of several types and consist of
syntactically allowed sequences of numbers, variables, operators,
left and right parentheses and commas. The most common types are as
follows:
2.8.1 Numerical Expressions
These consist of syntactically allowed combinations of
integer or real variables, arithmetic operators and parentheses, and
evaluate to numbers.
Examples:
2
I + J - 2 * I↑2
are numerical expressions if I and J are integers.
6
2.8.2 Boolean Expressions
These are expressions which return a truth value. In REDUCE,
the reserved word NIL represent the truth value 'false'. Any other
expression represents 'true'. So in a sense, any expression is a
boolean expression, because all expressions return a value. However,
a proper boolean expression has the syntactical form:
<expression> <relational operator> <expression>
or
<boolean expression> <logical operator> <boolean expression>
They are used mainly in the IF and FOR statements described in
Sections 2.10.2 and 2.10.3.
Examples:
J<1
3*X-1 >2
X > 0 ∨ X = -2
2.8.3 Symbolic Expressions
These consist of scalar variables and operators and follow
the normal rules of the LISP meta language.
Examples:
X
CAR U . REVERSE V
SIMP (U+V↑2)
2.8.4 Quoted Expressions
Because LISP evaluation requires that each variable or
expression have a value, it is necessary to add to REDUCE the concept
of a quoted expression by analogy with the LISP QUOTE function. This
is provided by the single quote mark '.
e. g. 'A represents the LISP S-expression (QUOTE A)
'(A B C) represents the LISP S-expression (QUOTE (A B C))
BEWARE!!! Within a quoted expression, normal LISP S-expression
syntax rules apply. Thus the escape character ! is just another LISP
character, as are the terminators ; and $. For example, 'A;
represents the S-expression (QUOTE A;), so you must put a space
before the semicolon if it is to act as a terminator.
2.8.5 LAMBDA Expressions
LAMBDA expressions provide the means for constructing LISP
LAMBDA expressions in symbolic mode. They may not be used in
algebraic mode.
7
Syntax:
<LAMBDA expression> ::= LAMBDA <varlist><terminator><statement>
<varlist> ::= (<variable>,...,<variable>)
e. g. LAMBDA (X,Y); CAR X . CDR Y
is equivalent to the LISP LAMBDA expression
(LAMBDA (X Y) (CONS (CAR X) (CDR Y)))
The parentheses may be omitted in specifying the variable
list if desired, and λ may be used in place of the reserved word
LAMBDA.
LAMBDA expressions may be used in symbolic mode in place of
prefix operators, or as an argument of the reserved word FUNCTION.
2.9 Reserved Words
Certain words are reserved in REDUCE. They may only be used
for the purpose intended as explained in the following sections.
These words are as follows:
<reserved word> ::= BEGIN|DO|ELSE|END|FOR|FUNCTION|IF|LAMBDA|NIL|
PRODUCT|RETURN|STEP|SUM|UNTIL|WHILE
2.10 Statements
A statement is any allowed combination of reserved words and
expressions, and has the syntax
<statement> ::= <expression>|<proper statement>
The following are some proper statements in REDUCE:
2.10.1 Assignment Statements
These statements have the following syntax
<assignment statement> ::= <expression> ← <statement>
In symbolic mode, if the left side of an assignment statement
is a variable, a SETQ of the right hand side to that variable occurs.
If the left hand side is an expression, a function definition is
assumed.
e. g. X←Y translates into (SETQ X Y)
whereas
ASSOC(U,V) ← IF NULL V THEN NIL
ELSE IF U≡ CAAR V THEN CAR V
ELSE ASSOC (U,CDR V)
8
defines the LISP function ASSOC.
MACROs and FEXPRs may be defined by prefixing the assignment
by the word MACRO or FEXPR.
e. g. we could define a MACRO CONSCONS by
MACRO CONSCONS L ← EXPAND(CDR L, 'CONS);
It is also possible to write an assignment in the form
<expression> ← <expression> ← ... ← <expression> ← <statement>
In this form, each <expression> is set to the value of the <statement>.
2.10.2 Conditional Statements
The conditional statement has the following syntax:
<conditional statement> ::= IF <boolean expression> THEN <statement>
ELSE <statement>
Its use is obvious. The ELSE clause is optional.
2.10.3 FOR Statements
The FOR statement is used to define a variety of program
loops. Its general syntax is as follows:
FOR <variable>←<arithmetic expression> STEP <arithmetic expression>
{UNTIL <arithmetic expression>} {
{ } {DO <statement>
{WHILE <boolean expression> } {
The FOR statement follows the normal ALGOL useage. It returns
the value NIL.
2.10.4 GO TO Statements
GO TO (or GOTO) statements are used to perform an
unconditional transfer to a label in a compound statement (Section
2.10.5). They have the syntax:
<go to statement> ::= GO TO <label>
<label> ::= <variable>
Restriction:
GO TO statements may only occur within a compound statement. They may
NOT occur at the top level of your program.
2.10.5 Compound Statements
A compound statement is defined by the following syntax
9
<compound statement> ::= BEGIN <compound tail>
<compound tail> ::= <unlabeled compound tail>
|<label>:<compound tail>
<unlabeled compound tail> ::= <statement> END
| <statement> <terminator> <compound tail>
<label> ::= <identifier>
<terminator> ::= ;|$
e. g. X ← BEGIN INTEGER M;
M←1$
L1: IF N=0 THEN RETURN M;
M←M*N$
N←N-1$
GO TO L1
END OF BLOCK;
will assign the factorial of a preassigned INTEGER N to X.
2.10.6 RETURN Statements
The RETURN statement allows for a transfer out of a compound
statement to the next highest program level. It may be used alone,
in which case the statement returns NIL.
e. g., RETURN (X+Y);
RETURN M;
RETURN;
Restriction:
RETURN statements may only occur within a compound statement.They may
NOT occur at the top level of your program.
2.11 Declarations
Declarations are a particular type of statement used to set
flags, make type declarations and define procedures. PROCEDURE
declarations are discussed in Section 2.16. Some other REDUCE
declarations are as follows:
2.11.1 Variable Type Declarations
These declarations tell the system how various identifiers
are to be processed. Types allowed include INTEGER, REAL and SCALAR.
e. g. INTEGER M,N;
REAL M1;
SCALAR X,Y;
Type declarations may be made at any level in a program, and apply
only to the particular program block in which they occur. Variables
not declared are assumed SCALAR. This is the basic algebraic variable
type.
10
2.11.2 Array declarations
Arrays in REDUCE are defined similar to FORTRAN dimension
statements.
e. g. ARRAY A(10),B(2,3,4);
Their indices each range from 0 to the value declared. An element of
an array is referred to in standard FORTRAN notation,
e. g. A(2)
Array elements may appear in the left side of assignment statements.
2.11.3 Mode Handling Declarations
Two declarations are offered to the user for turning on or
off a variety of flags in the system. The declarations ON and OFF
take a list of flag names as argument and turn them on and off
respectively.
e. g. ON ECHO;
OFF INT;
The use of these flags and others available to the user is
explained later in this manual.
2.12 Commands
A command is an order to the system to do something. It has
the syntax
<command> ::= <statement><terminator>|<proper command>
<proper command> ::= <command name><space>
<statement>,...,<statement><terminator>
A variety of commands are discussed in the sections which follow.
2.13 File Handling Commands
In many applications, it is desirable to load previously
prepared REDUCE files into the system, or to write output on varying
devices. REDUCE offers three commands for this purpose, namely, IN,
OUT, and SHUT.
2.13.1 IN
This command takes a list of file names as argument and
directs the system to input each file (which should contain REDUCE
commands) into the system. A file name will have a varying syntax
from implementation to implementation, but in many cases will be an
11
identifier.
e. g. IN F1,GGG; will load the files F1 and GGG.
When input comes from an external file, statements are echoed
on the output device as they are read. If this facility is not
required, the echoing can be prevented by turning off the flag ECHO
in the relevant file.
2.13.2 OUT
This command takes a single file name as argument, and
directs output to that file from then on. If the file has previously
been used for output during the current job, the output is appended
to the end of the file. An existing file is erased before its first
use for output in a job.
To output on the terminal without closing the output file,
the reserved file name T (for terminal) may be used.
e. g. OUT OFILE; will direct output to the file OFILE and
OUT T; will direct output the user's terminal.
2.13.3 SHUT
This command is used to close an output file at completion.
Most systems require this action by the user, otherwise output may be
lost. If a file is shut and a further OUT command issued for the
same file, the file is erased before the new output is written.
2.14 Procedures
It is often useful to name a statement for repeated use in
calculations with varying parameters, or to define operators.
REDUCE offers a procedural declaration for this purpose. Its general
syntax is:
<procedural type> PROCEDURE <name><varlist>;<statement>;
and
<varlist> ::= (<variable>,...,<variable>)
The types permitted are REAL, INTEGER, LISP (or SYMBOLIC), FEXPR and
MACRO. There is no default type in symbolic mode, i. e., a type must
always be included.
E. g., the example in Section 2.10.5 could be made into a INTEGER
procedure FAC by the declaration:
INTEGER PROCEDURE FAC (N);
BEGIN INTEGER M;
M←1$
L1: IF N=0 THEN RETURN M;
12
M←M*N$
N←N-1$
GO TO L1
END;
If we now evaluate FAC (3) we get the result 6.
Function definitions may also be input in a procedural form
The procedural type in this case is LISP (or SYMBOLIC). For example,
the definition of ASSOC in Section 2.10.1 could be written as
LISP PROCEDURE ASSOC(U,V);
IF NULL V THEN NIL
ELSE IF U≡ CAAR V THEN CAR V
ELSE ASSOC (U, CDR V);
FEXPRs and MACROS may also be input in this manner with the
procedural types FEXPR and MACRO respectively.
In order to allow users relatively easy access to the whole
REDUCE source program, system procedures are not protected against
user redefinition. If a procedure is redefined, a message
*** <procedure name> REDEFINED
is printed. If this occurs, and the user is not redefining his own
procedure, he is well advised to rename it!
2.15 Output of Strings
It is often useful to write a title or comment on output, or
name output expressions in a particular way. This is possible in
REDUCE by means of the command WRITE. The form of this command is
WRITE <expression>,...,<expression>;
where <expression> may be either a symbolic expression or a string
(Section 2.6). Strings are printed on output exactly as given except
for any characters which are ignored by the input scanner. Other
expressions are evaluated and their value printed.
The print line is closed at the end of the WRITE command
evaluation.
2.16 Commands Used in Interactive Systems
REDUCE is designed primarily for interactive use with a time-
shared computer, but naturally it can also operate in a batch
processing environment. There is a basic difference, however,
between interactive and batch use of the system. In the former case,
whenever the system discovers an ambiguity at some point in a
calculation, such as a forgotten type assignment for instance, it
13
asks the user for the correct interpretation. In batch operation, it
is not practical to terminate the calculation at such points and
require resubmission of the job, so the system makes the most obvious
guess of the user's intentions and continues the calculation.
If input is coming from an external file, the system treats
it as a batch processed calculation. If the user desires interactive
response in this case, he can turn on the flag INT in the file.
Likewise, he can turn off INT in the main program if he does not
desire continual questioning from the system.
Two commands are available in REDUCE for use in interactive
computing. The command PAUSE; may be inserted at any point in an
input file. When this command is encountered on input, the system
prints the message CONT? on the user's terminal and halts. If the
user responds Y (for yes), the calculation continues from that point
in the file. On the other hand, if the user responds N (for no),
control is returned to the terminal, and the user can input further
commands. However, later on he can use the command CONT;, and control
is then transferred back to the point in the file after the last
PAUSE was encountered.
2.17 SOS-Link
Facilities are present in REDUCE to allow users editing
access to program source files during calculations. To use these
facilities, all function definitions should be input from SOS files,
and global changes to these files, such as renumbering and insertion
of page marks, should be avoided.
There are two ways in which this link may be used. These are
as follows:
2.17.1 Correction of Input Errors
If an error is encountered on input while an SOS file is
being loaded, the system will print the error diagnostics, and then
print the message EDIT?. If the user types Y (for yes), the system
will then load SOS and print the line which marks the beginning of
the command in which the error occurred. The error can now be
corrected. After editing is complete, typing G (for go) in SOS has
the effect of closing the file, reloading your RLISP core image, and
rereading the input file from the beginning of the command where the
error occurred.
2.17.2 Editing Function Definitions
Any functions which were input to RLISP from an SOS file have
information saved with them which tells the system where they occur
in the file (this is why global changes to tthe source files should
be avoided). If the user desires to change the function definition
during an RLISP calculation, he can access the source definition in
14
the file by typing
EDIT <function name>;
This command causes SOS to be loaded and the first line of the
function printed. The user can now edit the function definition.
Typing G will cause the user's RLISP program to be reloaded, and the
altered function definition to be read from the file. Note, however,
that only one function may be redefined at a time by this method.
2.18 Debugging Facilities in REDUCE
A few simple debugging facilities are available in REDUCE for
the more experienced programmer. These are as follows:
2.18.1 Tracing Functions
A command TR is available in RLISP for tracing LISP function
calls. This command, and the associated commands UNTR, TRST and
UNTRST, are used in the form:
TR <function name>,<function name>,...,<function name>;
TR calls the LISP function TRACE, and its output is in exactly the
same form. The trace may be turned off by the function UNTR which
uses the LISP function UNTRACE.
WARNING:
Because LISP establishes fast links to functions in compiled
code once that code has been referenced, it is necessary to inhibit
this when tracing is required. TR does this as part of its
evaluation sequence, but if tracing is not required until late in a
program, the fast links already established by then may nullify the
trace. To prevent this, TR should be called with no arguments as the
first command in the program.
2.18.2 Tracing Assignments in Compound Statements
Useful diagnostic information can often be obtained by
observing the values which variables acquire during assignments in
particular functions. To do this in RLISP, one uses the command
TRST. There are some restrictions on the function names which appear
in the arguments of this function, however. First, the functions must
obviously be in the system in symbolic form; compiled functions no
longer contain information on the assignment variable names.
Secondly, the functions must have a compound statement at their top
level.
This particular trace may be turned off by the command
UNTRST.
15
2.19 END
The command END; is used to end external files which are used
as input to REDUCE. One of its purposes is to turn off the command
echo, which is annoying to a user typing at a terminal. However, it
also does some file control book-keeping (for example, any files
still open are automatically closed), and should therefore not be
omitted.
If an END command is used in the main program, control is
then transferred to LISP.
16
3. RUNNING REDUCE SYMBOLIC MODE ON THE STANFORD PDP-10
3.1 A symbolic mode version of REDUCE is stored as a 24K system
with filename RLISP.DMP.
REDUCE may be loaded by typing R RLISP. A message will then
inform you when the program is loaded. The system then expects REDUCE
commands from you. You can return to LISP by the command END;
If you require more core for your job, you can get it by
typing
↑C
.CORE <size required><cr>
.ST<cr>
You will then be back in REDUCE.
Alternatively, you can load the program initially with a larger core
size by typing
.R RLISP <core size><cr>
3.2 Special Features
3.2.1 If you give IN a variable or dotted pair as argument, the
system expects to find the file in your disk area, and similarly with
OUT. In addition, the reserved identifier L is used to represent the
line printer on output.
i. e. OUT L;
sends output to the line printer.
Input from other devices may be specified by preceding the
file name by the device name. For example, to input a file ANDY from
disk area [S,JAM] followed by FOO from DTA2:, you would type
IN (S,JAM),ANDY,DTA2!:,FOO;
3.2.2 The altmode character may be used as a terminator. This is very
convenient, as it is not then necessary to follow it by a carriage
return as is required with the other terminators. However, the value
of the symbolic evaluation is not printed in this case.
3.2.3 NOT
The character ¬ may be used interchangably with the unary
function NOT on input. On output, however, NOT is printed.
17
3.3 A SAMPLE PROGRAM
.R RLISP load the program
REDUCE 2 <system date>... system loaded
*COMMENT A SAMPLE PROGRAM; comments are allowed
*CAR ('(A)); compute the CAR of (A)
A here's its value
*ASSOC(U,V)←IF NULL V THEN NIL now define ASSOC
* ELSE IF U≡ CAAR V THEN CAR V
* ELSE ASSOC(U,CDR V);
*** ASSOC REDEFINED diagnostic message from REDUCE
ASSOC value from definition of ASSOC
*ASSOC ('A,'((B . C) (A . D))); test ASSOC
(A . D) it works!
*END; return to LISP
*** value of END routine
ENTERING LISP... so that you know
*
18
REFERENCES
[1] Hearn, A. C., REDUCE 2 User's Manual, Stanford Artificial
Intelligence Project Memo No. AIM-133 , October 1970.
[2] McCarthy, J., Abrahams, P. W., Edwards, D. J., Hart, T. P. and
Levin, M. I., LISP 1.5 Programmer's Manual, M.I.T. Press, 1965
[3] Weissman, Clark, LISP 1.5 Primer, Dickenson, 1967